//给你一个整数数组 nums 和一个 正整数 k 。 
//
// 请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。 
//
// 子数组是数组中的一个连续元素序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,3,2,3,3], k = 2
//输出：6
//解释：包含元素 3 至少 2 次的子数组为：[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 
//。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,4,2,1], k = 3
//输出：0
//解释：没有子数组包含元素 4 至少 3 次。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// 1 <= nums[i] <= 10⁶ 
// 1 <= k <= 10⁵ 
// 
//
// Related Topics 数组 滑动窗口 👍 46 👎 0

package leetcode.editor.cn;
//java:统计最大元素出现至少 K 次的子数组
public class Q2962CountSubarraysWhereMaxElementAppearsAtLeastKTimes {
    public static void main(String[] args){
        Solution solution = new Q2962CountSubarraysWhereMaxElementAppearsAtLeastKTimes().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public long countSubarrays(int[] nums, int k) {
        int n = nums.length, left = 0, max = 0;
        long res = 0, countK = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, nums[i]);
        }
        // 扩大右边界
        for (int right = 0; right < n; right++) {
            if (nums[right] == max) {
                countK++;
            }
            // 符合条件, 缩小左边界
            while (countK >= k) {
                if (nums[left] == max) {
                    countK--;
                }
                left++;
            }
            // right是子数组的右边界，左边界在[0, left - 1]的都符合条件
            res += left;
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}